The present invention relates to a nearest neighbor search method, more particularly to a computer-oriented fast search method of searching a set of real numbers for a real number closest to a query point (or real number) by the use of a prepared database of the real numbers.
In a computer simulation, a numerical analysis using a computer and the like, it is often required to search a large number of real numbers for a nearest neighbor to a query point (query number). For example, in the case of an aero-dynamical simulation, it is necessary to import surface coordinates of a moving body (Lagrangian elements) in the coordinate system of a structured grid (Euler elements).
In this case, if the number of real numbers to be searched is very large (for example more than one hundred million), the number of the query points is very large (for example more than one million), and/or the search is repeated a large number of times, then there is a possibility that the computing time reaches to several hours to a day.
Accordingly, in order to decrease such computing time and thereby to reduce the computational cost, many attempts have been proposed.
Heretofore, two types of methods have been employed in order to solve this kind of problem.
The first method is what is called whole search in which the query point q is compared with the sorted real numbers from the first real number x[1] to the last real number x[n] one by one until the magnitude relation is reversed. For example, if a real number x[ipoint] satisfying a condition:x[ipoint]≦q<x[ipoint+1]then the solution is this real number x[ipoint].
The second method is what is called bisection method or kd-tree method widely used in recent years as a more efficient method than the first method.
Furthermore, ANN (Approximate Nearest Neighbor) method which is a combination of the former two methods is also used in recent years.
However, in the above-mentioned methods (ANN, kd-tree), the advantageous effect decreases if the dimensions of the search points is increased to three dimensions because the difference from the whole search becomes small.
Further, as the dimensions are increased, the tree becomes complex, and the search ranges increase, therefore, the computing time increases.